package com.hdu.other.dp.three;

import java.util.HashMap;
import java.util.Map;

public class lc474 {
    class Solution {

        int oneCount = 0;
        int zeroCount = 0;
        final Map<String, Integer> CACHE_MAP = new HashMap<>();
        public int findMaxForm(String[] strs, int m, int n) {
            CACHE_MAP.clear();
            return f(
                    strs,
                    0,
                    m,
                    n
            );
        }

        int f(String[] strs, int index, int m, int n)
        {
            if (index == strs.length)
            {
                return 0;
            }
            String cacheKey = index + " " + m + " " + n;
            if (CACHE_MAP.containsKey(cacheKey))
            {
                return CACHE_MAP.get(cacheKey);
            }
            int ans = f(strs, index + 1, m, n);
            cal(strs[index]);
            if (m >= zeroCount && n >= oneCount)
            {
                ans = Math.max(f(strs, index + 1, m - zeroCount, n - oneCount) + 1, ans);
            }
            CACHE_MAP.put(cacheKey, ans);
            return ans;
        }

        void cal(String s)
        {
            int tmpOneCount = 0;
            int tmpZeroCount = 0;

            for (char c : s.toCharArray())
            {
                if (c == '0')
                {
                    tmpZeroCount++;
                }
                else
                {
                    tmpOneCount++;
                }
            }

            oneCount = tmpOneCount;
            zeroCount = tmpZeroCount;
        }
    }
}
